n=2000;
m=100;
w=[25,12,86,23,19,83,85,82,76,40,45,69,62,84,96,92,50,67,90,74,85,74,75,22,4,36,8,67,39,2,100,27,86,4,40,57,72,4,15,62,29,1,28,93,89,88,69,6,45,29,9,97,66,58,71,2,67,44,13,36,12,75,100,34,5,38,25,18,31,77,77,68,17,22,67,93,13,11,98,21,82,67,54,33,25,22,11,81,7,1,37,33,85,61,92,14,13,24,12,76,49,31,85,74,9,49,59,93,14,39,40,96,35,51,8,27,87,51,78,35,21,100,38,42,59,26,50,79,63,25,61,48,57,100,92,22,4,18,55,41,7,10,16,33,35,47,5,75,20,100,56,8,35,24,54,71,74,41,41,13,30,6,43,78,60,98,11,93,87,59,50,68,89,36,76,62,72,46,88,29,63,73,89,48,33,49,75,79,41,95,69,68,83,90,80,58,33,21,24,67,70,98,58,28,91,7,74,24,23,37,57,57,64,87,61,38,86,52,4,12,48,47,66,99,77,93,75,35,61,67,77,64,52,58,74,27,22,61,24,59,59,67,20,18,13,32,16,67,91,100,61,36,24,9,100,31,97,63,16,43,72,90,48,8,62,20,41,58,61,46,44,74,41,48,41,53,3,82,34,91,36,57,81,4,69,65,4,96,47,41,4,32,29,82,15,22,79,63,21,65,65,52,48,54,52,16,60,26,73,85,24,70,64,79,50,51,26,48,40,22,58,62,89,11,40,13,57,67,11,23,89,80,98,17,50,80,69,8,38,53,65,68,28,68,43,87,67,7,44,1,5,13,15,59,4,39,87,1,46,12,56,69,69,22,27,88,97,6,56,83,81,70,63,71,23,84,34,96,48,14,14,76,63,72,97,54,65,94,87,41,25,86,68,27,1,96,64,62,1,52,36,65,78,32,60,10,50,55,21,47,89,37,1,42,75,40,5,69,37,42,7,38,68,64,23,24,42,58,95,74,38,48,89,3,38,81,88,46,79,53,75,79,39,28,9,6,67,97,98,20,66,69,13,43,46,53,94,41,94,56,9,8,84,21,20,12,11,47,18,54,52,86,29,20,60,91,49,92,65,55,93,81,46,45,49,52,99,96,5,92,46,18,41,24,51,70,57,65,3,43,99,18,71,70,2,34,29,50,42,1,27,66,30,26,23,62,32,5,64,74,39,52,66,96,97,95,43,32,19,28,32,5,18,35,74,17,43,42,7,48,15,76,79,81,72,87,91,34,86,55,7,71,73,21,7,25,21,72,68,43,15,35,68,52,68,44,28,78,88,59,4,51,32,73,40,26,7,22,24,88,10,97,33,39,2,32,67,30,38,84,99,46,13,9,58,61,52,65,36,78,60,29,77,41,7,61,2,27,48,25,48,11,76,8,42,69,83,8,32,23,40,37,6,87,68,3,69,93,47,62,64,5,48,93,35,87,50,19,49,13,31,75,2,40,98,38,67,55,63,37,32,64,98,49,26,12,28,100,83,26,69,44,79,23,23,18,33,12,17,3,36,83,15,21,78,31,93,53,6,23,11,100,81,36,21,84,28,6,34,72,31,96,73,98,77,95,85,32,42,94,9,17,81,75,85,34,12,27,92,97,89,42,87,40,42,45,24,16,14,57,46,28,57,89,60,21,22,23,24,92,84,27,26,74,36,59,81,50,24,62,29,88,14,48,78,61,26,77,100,31,18,21,19,30,25,11,33,24,78,41,86,85,30,96,79,33,83,12,70,98,18,14,44,92,43,76,56,95,63,9,80,61,39,94,30,72,11,24,73,27,5,26,75,55,96,1,88,63,71,46,4,68,46,24,22,20,3,72,23,71,28,69,69,12,8,3,46,46,75,38,31,62,64,54,52,10,18,98,79,10,80,9,1,82,8,12,19,61,53,46,68,45,13,41,47,74,55,17,24,31,26,54,68,42,81,5,37,55,11,94,50,5,58,53,94,52,88,54,98,14,87,79,38,63,94,56,65,78,79,72,84,7,86,23,51,22,49,94,37,53,10,87,9,81,18,97,45,21,51,14,32,55,96,23,71,7,91,39,19,1,72,40,61,78,64,87,89,34,57,42,20,97,28,23,69,56,70,2,74,57,43,39,32,77,36,65,27,16,80,30,11,62,62,33,19,49,49,68,66,91,95,37,76,6,62,3,53,57,92,28,89,28,30,98,83,11,31,31,95,90,13,57,46,97,77,94,15,79,75,79,1,16,53,7,18,64,56,83,22,88,58,39,21,27,22,47,13,5,1,47,83,26,63,68,11,14,41,72,25,60,100,20,27,77,17,12,53,79,74,34,48,34,78,35,62,73,81,94,21,47,66,10,58,15,80,63,92,38,78,88,52,45,22,7,47,55,41,51,75,24,93,54,70,21,90,19,25,50,49,99,83,74,46,20,77,10,33,61,21,68,80,95,89,45,63,11,6,5,44,62,4,98,71,53,9,92,4,33,50,3,56,45,12,33,62,49,55,89,7,71,35,85,67,20,20,36,22,26,55,63,9,79,85,29,50,32,88,28,23,51,64,2,5,98,32,80,60,1,65,62,32,53,14,43,28,22,16,55,78,58,55,78,22,79,50,6,20,47,72,27,83,22,20,50,55,80,38,88,25,87,2,1,26,19,9,44,49,68,77,33,1,76,38,41,30,6,58,80,55,34,69,28,56,61,93,40,80,64,35,68,6,20,87,100,52,36,45,4,84,23,24,62,2,60,11,56,81,75,26,63,77,20,22,52,42,54,20,98,99,9,99,80,17,48,63,21,89,90,57,77,15,27,5,30,77,81,23,3,23,36,57,64,56,87,87,62,77,23,24,7,52,65,49,97,4,91,68,51,99,19,18,1,96,20,55,18,38,97,61,43,68,11,16,13,11,97,93,98,25,61,86,48,23,62,9,98,45,5,55,7,61,84,11,24,73,45,67,5,13,50,22,47,28,21,22,45,46,71,72,48,54,96,14,60,80,21,48,11,86,13,78,64,67,29,57,36,96,84,92,96,10,37,41,32,80,62,56,49,77,80,3,77,60,92,35,79,44,82,70,41,70,12,41,30,93,54,20,43,12,51,7,21,89,6,63,56,66,29,18,79,72,18,99,60,8,21,70,5,77,5,90,39,5,66,76,69,95,42,67,60,1,67,44,78,59,61,72,93,63,56,99,14,11,27,19,17,24,50,98,27,96,66,29,65,67,43,69,46,49,98,10,12,39,88,58,91,6,89,59,95,76,45,52,31,94,72,60,17,73,88,20,68,34,100,82,24,27,15,35,48,75,82,3,38,6,41,29,7,71,67,88,20,79,37,48,100,1,73,94,35,80,48,27,40,1,56,18,2,27,89,72,96,13,70,99,54,78,88,63,74,75,23,68,10,46,40,52,88,60,34,32,59,71,75,4,56,94,42,48,61,71,43,76,65,15,94,69,89,63,27,85,32,20,5,79,17,43,66,87,52,51,11,95,90,4,88,23,51,58,82,21,41,61,55,97,99,86,38,83,13,69,95,18,18,28,49,40,35,12,62,30,82,99,47,42,39,70,5,47,93,52,88,29,61,34,78,8,98,8,69,89,12,36,96,35,58,30,43,80,6,52,18,53,61,14,76,5,30,24,20,100,43,19,55,3,17,26,63,8,95,82,16,8,14,36,6,3,83,45,58,35,17,98,84,47,1,22,44,30,96,24,55,60,56,17,36,84,17,37,36,18,81,93,51,36,58,74,68,48,74,71,91,12,65,84,21,96,39,61,24,63,84,53,43,60,48,53,35,15,82,100,87,21,8,4,74,72,64,20,32,82,81,91,90,63,57,41,89,77,78,57,3,92,18,67,48,31,99,83,76,85,75,45,82,83,93,62,32,28,28,75,48,78,47,69,19,77,13,69,19,22,78,81,27,82,66,18,73,55,82,79,3,53,4,74,51,32,43,65,63,22,91,76,37,32,9,81,2,86,34,64,13,18,32,84,22,69,9,54,91,72,32,61,44,56,94,45,30,89,30,92,21,8,72,22,22,31,66,59,42,29,58,22,73,46,54,40,73,32,38,95,79,15,46,97,18,2,40,56,25,26,86,66,83,54,35,12,65,52,10,79,100,51,79,71,40,78,63,100,80,55,90,53,79,40,47,75,58,74,86,2,10,10,8,69,45,97,56,80,96,94,65,33,24,71,25,72,26,41,96,96,35,64,80,13,7,26,55,27,24,61,21,74,67,66,47,24,87,17,56,53,81,18,48,65,78,50,43,83,74,51,91,80,9,92,100,85,17,9,50,37,56,26,12,66,74,5,24,7,44,65,67,62,90,72,2,64,82,24,53,65,70,21,11,84,100,14,54,50,95,87,41,38,17,9,35,37,16,32,14,38,73,5,63,37,27,95,68,4,39,64,23,7,100,83,17,56,54,8,59,85,67,41,99,8,25,56,14,7,48,11,25,94,14,70,2,37,6,51,44,6,47,22,98,31,85,92,27,92,40,30,42,100,91,82,88,12,10,17,18,68,28,25,57,25,95,68,15,22,69];